/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package lab2;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 * @author rafael
 */
public class Grafo {
    private List<No> vertices;

	public static Grafo criarGrafo()
	{
		Grafo grf = new Grafo();
		grf.vertices = new ArrayList<No>();
                for(int i=0;i<5;i++)
                {
                    char c = (char)(97+i);
                    grf.vertices.add(new No(""+c));
                }
                grf.vertices.get(0).addConexao(grf.vertices.get(2), 2);//ab
                grf.vertices.get(2).addConexao(grf.vertices.get(0), 2);//ba
                grf.vertices.get(0).addConexao(grf.vertices.get(1), 4);//ac
                grf.vertices.get(1).addConexao(grf.vertices.get(0), 4);//ca
                grf.vertices.get(1).addConexao(grf.vertices.get(2), 5);//bc
                grf.vertices.get(2).addConexao(grf.vertices.get(1), 5);//cb
                grf.vertices.get(1).addConexao(grf.vertices.get(3), 7);//bd
                grf.vertices.get(3).addConexao(grf.vertices.get(1), 7);//db
                grf.vertices.get(2).addConexao(grf.vertices.get(3), 8);//cd
                grf.vertices.get(3).addConexao(grf.vertices.get(2), 8);//dc
                grf.vertices.get(4).addConexao(grf.vertices.get(3), 1);//ed
                grf.vertices.get(3).addConexao(grf.vertices.get(4), 1);//de
		return grf;
	}
        public No getNo(String desc)
        {
            No retorno = null;
            for(No u : this.vertices)
            {
                if(u.getDescricao().equals(desc))
                {
                    retorno = u;
                }
            }
            return retorno;
        }
        public void getNos()
        {
            for(No u : this.vertices)
            {
                if(u!=null)
                {
                    System.out.println(u.getDescricao());
                }
            }
        }
	public int menorCaminho(No u, No w)
	{
            Queue<No> fila = new LinkedList<No>();
            if(!fila.offer(u)) throw new NullPointerException();
            u.setDistancia(0);
            while(!fila.isEmpty())
            {
                No v = fila.poll();
                for( Aresta x : v.getArestas())
                {
                    No k = x.getDestino();
                    if(k.getDistancia() == -1 || k.getDistancia()>x.getPeso()+v.getDistancia())
                    {
                        k.setDistancia(x.getPeso()+v.getDistancia());
                    }
                    if(!fila.offer(k)) throw new NullPointerException();
                }
            }
            return w.getDistancia();
	}
}
